package leetcode.editor.cn;

//给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。 
//
// 示例 1: 
//
// 
//输入: "abab"
//
//输出: True
//
//解释: 可由子字符串 "ab" 重复两次构成。
// 
//
// 示例 2: 
//
// 
//输入: "aba"
//
//输出: False
// 
//
// 示例 3: 
//
// 
//输入: "abcabcabcabc"
//
//输出: True
//
//解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
// 
// Related Topics 字符串 字符串匹配 👍 588 👎 0

import java.util.Arrays;

//Java：重复的子字符串
public class RepeatedSubstringPattern_459{
    public static void main(String[] args) {
        Solution solution = new RepeatedSubstringPattern_459().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        char[] ss = s.toCharArray();
        int[] next = new int[len];
        for (int i = 1,j=0; i < len; i++) {
            while(j>0 && ss[i]!=ss[j])
                j=next[j-1];
            if(ss[i]==ss[j]) j++;
            next[i] = j;
        }
//        System.out.println(Arrays.toString(next));
        if(next[len-1]==0) return false; //没有最长前缀
        if(len % (len - next[len-1]) == 0) return true;
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
